package Offertuji;

public class Offer2001 {
    /*剑指 Offer II 001. 整数除法
    给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
    整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8以及truncate(-2.7335) = -2
    假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,231−1]。本题中，如果除法结果溢出，则返回 231− 1
    示例 1：

    输入：a = 15, b = 2
    输出：7
    解释：15/2 = truncate(7.5) = 7
    示例 2：

    输入：a = 7, b = -3
    输出：-2
    解释：7/-3 = truncate(-2.33333..) = -2
    示例 3：

    输入：a = 0, b = 1
    输出：0
    示例 4：

    输入：a = 1, b = 1
    输出：1

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/xoh6Oh
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

     */
    public int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1)
            return Integer.MAX_VALUE;
        if(b==0)
        {
            return 0;
        }
        int sign = (a>0)^(b>0)? -1:1;
        if(a>0)
            a=-a;
        if(b>0)
            b=-b;
        int c = a;
        int i = 0;
        while(c<b){
            c=a-b;
            i++;
        }
        return sign==1?i:-i;

    }//自己做的超时了
    public int divide1(int a, int b) {
        int flag = 0;
        if (a > 0) {
            a = -a;
            flag += 1;
        }

        if (b > 0) {
            b = -b;
            flag += 1;
        }
        int ret = calc(a, b);
        if (flag != 1 && ret == Integer.MIN_VALUE) {
            ret++;
        }
        return flag == 1 ? ret : -ret;
    }

    private int calc(int a, int b) {
        int ret = 0;
        while (a <= b) {
            int cnt = 1;
            int val = b;
            while (val >= Integer.MIN_VALUE >> 1  && a <= val << 1) {
                cnt += cnt;
                val += val;
            }
            ret -= cnt;
            a -= val;
        }
        return ret;
    }//标准答案

}
